# 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
# 输入: nums = [1,2,3,4,5,6,7], k = 3
# 输出: [5,6,7,1,2,3,4]
from typing import List


# 空间复杂度O(n)，时间复杂度O(n)
# 使用了额外的数组
def rotate(nums: List[int], k: int) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    num_length = len(nums)
    k_index = k % num_length
    left = nums[-k_index:]
    right = nums[0: num_length - k_index]
    result = left + right
    for i in range(num_length):
        nums[i] = result[i]


# 使用一个变量，旋转替换的方式
def rotate_replace(nums: List[int], k: int) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """

    nums_length = len(nums)
    # 用来统计挪了多少个位置
    count = 0

    for first_index in range(nums_length):
        # 下一个位置的索引
        next_index = (first_index + k) % nums_length

        # 拿出来后面的数
        temp_num = nums[first_index]

        while next_index != first_index:
            # 防止下一个元素被覆盖，临时变量保存一下
            temp = nums[next_index]
            nums[next_index] = temp_num
            next_next_index = (next_index + k) % nums_length
            temp_num = temp
            next_index = next_next_index
            count += 1

        nums[first_index] = temp_num
        count += 1
        if count == nums_length:
            return


# 翻转数组的方式
# 步骤1）翻转整个数组[0,length-1]
# 步骤2）翻转[0,k-1]
# 步骤3）翻转[k,length-1]
def rotate_rotate(nums: List[int], k: int) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """

    def inner_rotate(nums: List[int], left: int, right: int):
        half = (left + right) // 2
        for i in range(left, half + 1):
            target = left + right - i
            temp = nums[i]
            nums[i] = nums[target]
            nums[target] = temp

    inner_rotate(nums, 0, len(nums) - 1)
    inner_rotate(nums, 0, k % len(nums) - 1)
    inner_rotate(nums, k % len(nums), len(nums) - 1)


nums_1 = [1, 2, 3, 4, 5, 6]
k_1 = -7
rotate_rotate(nums_1, k_1)
print(nums_1)
